package com.xieyong.leetcode;

import java.util.*;

public class Leetcode1353 {
    public static void main(String[] args) {
        Leetcode1353 leetcode1353 = new Leetcode1353();
        int[][] events = {{1,2},{1,2},{3,3},{1,5},{1,5}};
        long startTime = System.currentTimeMillis();
        int i = leetcode1353.maxEvents(events);
        long endTime = System.currentTimeMillis();
        System.out.println(i);
        System.out.println(endTime - startTime);

    }
    public int maxEvents(int[][] events) {
        int n = events.length;
        int maxday = 0;
        for (int[] event : events) {
            maxday = Math.max(maxday, event[1]);
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        Arrays.sort(events,(a,b) -> a[0] - b[0]);
        int res = 0;
        for (int i = 1, j = 0; i <= maxday; i++) {
            while (j < n && events[j][0] <= i) {
                pq.offer(events[j][1]);
                j++;
            }
            while (!pq.isEmpty() && pq.peek() < i) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                pq.poll();
                res++;
            }
        }
        return res;
    }

// 超时
//    public int maxEvents(int[][] events) {
//        List<Integer[]> list = new ArrayList<>();
//        int maxday = 0;
//        for (int[] event : events) {
//            maxday = Math.max(maxday, event[1]);
//            list.add(new Integer[]{event[0], event[1]});
//        }
//        list.sort(new Comparator<Integer[]>() {
//            @Override
//            public int compare(Integer[] o1, Integer[] o2) {
//                int s1 = o1[0] * 1000000 + o1[1];
//                int s2 = o2[0] * 1000000 + o2[1];
//                return s1 - s2;
//            }
//        });
//        int res = 0;
//        int day = 1;
//        while (day <= maxday) {
//            List<Integer[]> list2 = new ArrayList<>();
//            for (Integer[] integers : list) {
//                if (integers[0] <= day && integers[1] >= day) {
//                    list2.add(integers);
//                }
//            }
//            if (!list2.isEmpty()) {
//                list2.sort(new Comparator<Integer[]>() {
//                    @Override
//                    public int compare(Integer[] o1, Integer[] o2) {
//                        return o1[1] - o2[1];
//                    }
//                });
//                Integer[] integers = list2.get(0);
//                res++;
//                list.remove(integers);
//            }
//            day++;
//        }
//        return res;
//    }
}
